#include<bits/stdc++.h>
using namespace std;
const int N=1e7+1;
int p[N],cnt,s[N]; 
int q,a[5],vis[5];
long long ans;
void dfs(int x,long long dis){
	if(dis>=ans) return;
	if(x==1){
		ans=dis;
		return;
	}
	for(int i=1;i<=4;++i)if(!vis[i]){
		vis[i]=1;
		dfs(i,dis+1ll*a[x]*a[i]/__gcd(a[x],a[i]));
		vis[i]=0;
	}
}
int main(){
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout);
	for(int i=2;i<N;++i){
		if(!s[i]) s[i]=i,p[++cnt]=i;
		for(int j=1;j<=cnt&&p[j]*i<N;++j){
			s[i*p[j]]=min(s[i],p[j]);
			if(i%p[j]==0) break;
		}
	}
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&a[0],&a[1]);
		if(a[1]%a[0]==0){
			printf("%d\n",a[1]);
			continue;
		}if(__gcd(a[0],a[1])!=1){
			printf("%d\n",a[0]+a[1]);
			continue;
		}
		a[2]=2,a[3]=s[a[0]],a[4]=s[a[1]];
		memset(vis,0,sizeof(vis));
		ans=1e18;
		dfs(0,0);
		printf("%lld\n",ans);
	}
	return 0;
}

